package com.mamingchao.foundation.arraysort.shellsort;

/**
 * 升级版的 插入排序
 * 在 执行插入排序之前，先把间隔着的元素 做个插入排序
 *
 * 不过，最后一定要 做一个原始的插入排序（无间隔的）
 * Created by mamingchao on 2021/3/9.
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {5,3,6,1,8,2,1,0,12,13,17,9,20,30};

//        for (int i = 4; i < arr.length; i++) {
//            for (int j = i; j > 3; j=j-3) {
//                if (arr[j] < arr[j-3]) {
//                    arr[j] = arr[j] ^ arr[j-3];
//                    arr[j-3] = arr[j] ^ arr[j-3];
//                    arr[j] = arr[j] ^ arr[j-3];
//                } else {
//                    break;
//                }
//            }
//        }
//
//        for (int i = 2; i < arr.length; i++) {
//            for (int j = i; j > 1; j=j-2) {
//                if (arr[j] < arr[j-2]) {
//                    arr[j] = arr[j] ^ arr[j-2];
//                    arr[j-2] = arr[j] ^ arr[j-2];
//                    arr[j] = arr[j] ^ arr[j-2];
//                } else {
//                    break;
//                }
//            }
//        }
//
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j > 0; j=j-1) {
//                if (arr[j] < arr[j-1]) {
//                    arr[j] = arr[j] ^ arr[j-1];
//                    arr[j-1] = arr[j] ^ arr[j-1];
//                    arr[j] = arr[j] ^ arr[j-1];
//                } else {
//                    break;
//                }
//            }
//        }

        sort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }

    public static void sort(int[] arr) {
        for (int h = arr.length >> 1; h > 0 ; h/=2) {
            System.out.println("h 的值为-" + h);
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h-1; j=j-h) {
                    if (arr[j] < arr[j-h]) {
                        arr[j] = arr[j] ^ arr[j-h];
                        arr[j-h] = arr[j] ^ arr[j-h];
                        arr[j] = arr[j] ^ arr[j-h];
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
